package middle;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution_128 {

    public int longestConsecutive(int[] nums) {
        int[] counts = new int[nums.length];
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Set<Integer> set = map.getOrDefault(nums[i], new HashSet<>());
            set.add(i);
            map.put(nums[i], set);
        }
        int max = 0;
        for (int num : nums) {
            int dps = dps(counts, num, map);
            if (max < dps) {
                max = dps;
            }
        }
        return max;
    }

    private int dps(int[] counts, int num, Map<Integer, Set<Integer>> map) {
        if (map.containsKey(num)) {
            int rst = 1;
            Set<Integer> set = map.get(num);
            for (Integer index : set) {
                if (counts[index] > 0) {
                    return counts[index];
                }
                int count = dps(counts, num - 1, map);
                counts[index] = count + 1;
                rst = counts[index];
            }
            return rst;
        }
        return 0;
    }

    public int longestConsecutive1(int[] nums) {
        if (nums.length==0) {
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int maxCount = 0;
        for (int num : nums) {
            if (!set.contains(num-1)) {
                int count = 0;
                int val = num;
                while (set.contains(val++)) {
                    count++;
                }
                maxCount = Math.max(count, maxCount);
            }
        }
        return maxCount;
    }

    public static void main(String[] args) {
        Solution_128 model = new Solution_128();
        System.out.println(model.longestConsecutive(new int[]{100,4,200,1,3,2}));
        System.out.println(model.longestConsecutive(new int[]{0,3,7,2,5,8,4,6,0,1}));
    }
}
